/**
 * 银行家算法(Banker's algorithm)实现
 * @author 何茂旗
 * @date 2020-9-29
 */

#include <stdio.h>
// 进程数量
#define NUMBER_OF_PROCESSES 5
// 资源数量
#define NUMBER_OF_RESOURCE_TYPES 3
// 定义 boolean 类型
#define true 1
#define false 0
typedef int bool;

/******** 全局变量声明 ********/
// 可利用资源向量
int available[NUMBER_OF_RESOURCE_TYPES] = { 3, 3, 2 };
// 最大需求矩阵
int max[NUMBER_OF_PROCESSES][NUMBER_OF_RESOURCE_TYPES] = {
  { 7, 5, 3 },
  { 3, 2, 2 },
  { 9, 0, 2 },
  { 2, 2, 2 },
  { 4, 3, 3 }
};
// 已分配矩阵
int allocation[NUMBER_OF_PROCESSES][NUMBER_OF_RESOURCE_TYPES] = {
  { 0, 1, 0 },
  { 2, 0, 0 },
  { 3, 0, 2 },
  { 2, 1, 1 },
  { 0, 0, 2 }
};
// 需求矩阵
int need[NUMBER_OF_PROCESSES][NUMBER_OF_RESOURCE_TYPES] = {
  { 7, 4, 3 },
  { 1, 2, 2 },
  { 6, 0, 0 },
  { 0, 1, 1 },
  { 4, 3, 1 }
};

/******** 函数声明 ********/
bool request(int *request_resources, int process_id);
bool safe_check();

/******** 主函数 ********/
int main() {
  // 初始检查系统是否为安全状态
  printf("initial check: ");
  printf(safe_check() ? "safe" : "not safe");
  printf("\n");
  // P1 进程请求资源
  int resource_request_1[3] = { 1, 0, 2 };
  printf("P1 request: ");
  printf(request(resource_request_1, 1) ? "successful" : "failed");
  printf("\n");
  // P4 进程请求资源
  int resource_request_2[3] = { 3, 3, 0 };
  printf("P4 request: ");
  printf(request(resource_request_2, 4) ? "successful" : "failed");
  printf("\n");
  // P0 进程请求资源
  int resource_request_3[3] = { 0, 2, 0 };
  printf("P0 request: ");
  printf(request(resource_request_3, 0) ? "successful" : "failed");
  printf("\n");
  // 最后检查系统状态
  printf("last check: ");
  printf(safe_check() ? "safe" : "not safe");
  printf("\n");
  return 0;
}

bool request(int *request_resources, int process_id) {
  /*
   * 进程请求资源
   * @param { int[] } request_resources 请求资源向量
   * @param { int } process_id 请求进程 id(上述某矩阵的行索引)
   * @return { bool } 申请资源是否成功
   */
  
  // 检查对每个资源的请求是否超过其自身需求
  for (int resource_type = 0; resource_type < NUMBER_OF_RESOURCE_TYPES; resource_type++) {
    if (need[process_id][resource_type] < request_resources[resource_type]) { return false; }
  }

  // 检查对每个资源的请求是否超过可用资源总数
  for (int resource_type = 0; resource_type < NUMBER_OF_RESOURCE_TYPES; resource_type++) {
    if (available[resource_type] < request_resources[resource_type]) { return false; }
  }

  // 尝试分配资源
  for (int resource_type = 0; resource_type < NUMBER_OF_RESOURCE_TYPES; resource_type++) {
    available[resource_type] -= request_resources[resource_type];
    allocation[process_id][resource_type] += request_resources[resource_type];
    need[process_id][resource_type] -= request_resources[resource_type];
  }

  // 检查系统是否处于安全状态, 不安全回滚, 分配失败
  bool is_safe = safe_check();
  if (!is_safe) {
    // 回滚
    for (int resource_type = 0; resource_type < NUMBER_OF_RESOURCE_TYPES; resource_type++) {
      available[resource_type] += request_resources[resource_type];
      allocation[process_id][resource_type] -= request_resources[resource_type];
      need[process_id][resource_type] += request_resources[resource_type];
    }
  }
  return is_safe;
}

bool safe_check() {
  /*
   * 安全性检查
   * @return { bool } 系统是否处于安全状态
   */

  // 系统可提供给进程继续运行的所需各类资源数目
  int work[NUMBER_OF_RESOURCE_TYPES];
  for (int resource_type = 0; resource_type < NUMBER_OF_RESOURCE_TYPES; resource_type++) { work[resource_type] = available[resource_type]; }
  // 是否可以分配资源
  int finish[NUMBER_OF_PROCESSES] = { false };
  // 用于统计 finish 向量中值为 true 的元素个数
  int number_of_finished = 0;

  while (number_of_finished < NUMBER_OF_PROCESSES) {
    for (int process_id = 0; process_id < NUMBER_OF_PROCESSES; process_id++) {
      // 判断是否满足条件
      bool is_meet_need = true;
      for (int resource_type = 0; resource_type < NUMBER_OF_RESOURCE_TYPES; resource_type++) {
        if (need[process_id][resource_type] > work[resource_type]) { is_meet_need = false; break; }
      }
      if (finish[process_id] || !is_meet_need) {
        if (process_id == NUMBER_OF_PROCESSES - 1) {
          // 所有进程都无法满足, 不安全状态
          return false;
        } else { continue; }
      }

      // 满足条件, 尝试分配资源并释放
      for (int resource_type = 0; resource_type < NUMBER_OF_RESOURCE_TYPES; resource_type++) {
        work[resource_type] += allocation[process_id][resource_type];
      }
      finish[process_id] = true;
      number_of_finished++;
      break;
    }
  }
  return true;
}
